package com.rr.middle;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhuangcanrun
 * @Date 2022/08/03/18:59
 * @description
 **/
/*
* https://leetcode.cn/problems/insert-interval/submissions/
* */
public class Insert {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int left = newInterval[0];
        int right = newInterval[1];
        boolean hadReplace = false;
        List<int[]> list = new ArrayList<>();
        for (int[] interval : intervals) {
            if (right < interval[0]) {
                //说明要插入的interval已经在当前interval前面
                if (!hadReplace) {
                    //如果还没插入，需要将前面更新合并后的interval插入
                    list.add(new int[]{left, right});
                    hadReplace = true;
                }
                //把当前的interval插入
                list.add(interval);
            } else if (left > interval[1]) {
                //说明要插入的interval还在当前interval后面，插入当前interval
                list.add(interval);
            } else {
                //进到这里说明有交集，更新下要插入的interval的大小
                left = Math.min(left, interval[0]);
                right = Math.max(right, interval[1]);
            }
        }
        if (!hadReplace) {
            list.add(new int[]{left, right});
        }
        int size = list.size();
        int[][] ans = new int[size][2];
        for (int i = 0; i < size; i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }
}
